def helper(nums: list[int], left: int, right: int):
    """递归二分排序"""
    if left >= right:
        return

    # 哨兵划分：默认选择 nums[left] 作为基准数，基准数越靠近中位数越好
    i, j = left, right
    while i < j:
        while i < j and nums[j] >= nums[left]:
            j -= 1
        while i < j and nums[i] <= nums[left]:
            i += 1
        nums[i], nums[j] = nums[j], nums[i]
    nums[i], nums[left] = nums[left], nums[i]

    # 递归处理
    pivot = i
    helper(nums, left, pivot - 1)
    helper(nums, pivot + 1, right)


def quick_sort(nums: list[int]):
    """快速排序"""
    helper(nums, 0, len(nums) - 1)


if __name__ == "__main__":
    nums = [4, 1, 3, 1, 5, 2, 9, 8, 6, 7]
    quick_sort(nums)
    print("排序完成后 nums =", nums)
    # 排序完成后 nums = [1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
